/******************************************************************************
                         COPYRIGHT 1955-2008 by BUPT ISC.
                        北京邮电大学信息安全中心 版权所有
                           Web: http://www.bupt.edu.cn
 *******************************************************************************/
/*******************************************************************************
  文件名： hash.c
  项目：   
  模块：   common
  作者：   huangwei
  版本：   0.3
  创建于:  2008-11-04 
  描述：
    Hash表的操作方法实现

  修改历史： 
  日期：     修改人：     修改描述：
  09/04/27   jiangwen     修改resizeHash函数，对Hash容量实现每次递增
  09/05/07   huangwei     修改deleteHash函数，增加一个参数用于判断是否是
                          resizeHash函数的调用，避免对同一块堆内存释放两次 
  09/05/14   huangwei     1.修改removeBucketInHash和removeHash函数的实现                        
                          2.函数返回值都改为void
                          3.removeBucketInHash时先判断Hash表节点中的数据是否需要先
                            释放内存，避免可能的内存泄漏
                          4.修正了部分函数的注释
 *********************************************************************************/

#include <stdio.h>
#include <string.h>
#include <stdint.h>

#include "hash.h"
#include "log.h"

static void freeHash(HASH_TABLE_T *pstHash);


/******************************************************************************
  函数名：initHash
  功能描述：
    初始化并清空Hash表

  输入参数：
    HASH_TABLE_T * 待初始化Hash表指针

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
void initHash(HASH_TABLE_T *pstHash)
{
    int i;
    pstHash->iElements = 0;
    for (i = 0; i < pstHash->iSize; i++)
    {
        pstHash->pstTable[i] = NULL;
    }

}

/******************************************************************************
  函数名：deleteHash
  功能描述：
    删除Hash表，并调用HASH_FREE_CB函数清空Hash节点所占用的内存

  输入参数：
    HASH_TABLE_T * 待释放内存的Hash表指针
    int            是否调用Hash表中的内存释放函数

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
void deleteHash(HASH_TABLE_T *pstHash, int iEnableFreeCb)
{
    if (pstHash == NULL)
    {
        return;
    }
    HASH_NODE_T *pstBucket;
    HASH_NODE_T *pstLastBucket;
    HASH_FREE_CB pfnFreeCb = pstHash->pfnFree;
    int i;

    for (i = 0; i < pstHash->iSize; i++)
    {
        pstBucket = pstHash->pstTable[i];
        while (pstBucket != NULL)
        {
            if (pfnFreeCb != NULL && iEnableFreeCb)
            {
                pfnFreeCb( pstBucket->pData );
            }
            pstLastBucket = pstBucket;
            pstBucket = pstBucket->pstNext;
            free(pstLastBucket);
        }
    }
    freeHash(pstHash);

}

/******************************************************************************
  函数名：freeHash
  功能描述：
    释放HASH_TABLE_T指针所占用的内存
    Hash表内的Hash节点的内存释放需要调用deleteHash函数

  输入参数：
    HASH_TABLE_T * 待释放内存的Hash表指针

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
static void freeHash(HASH_TABLE_T *pstHash)
{
    if (pstHash != NULL)
    {
        if(pstHash->pstTable != NULL)
        {
            free(pstHash->pstTable);
            pstHash->pstTable = NULL;
        }

        free(pstHash);
        pstHash = NULL;
    }
}

/******************************************************************************
  函数名：iterateHash
  功能描述：
     遍历Hash表中所有元素。当pstHashIt参数为NULL时返回Hash表中第一个元素对应
     的迭代器。使用这个返回的迭代器作为参数pstHashIt，递归调用本函数将遍历Hash
     表。当迭代完最后一个元素之后，将返回NULL。
    
  输入参数：
    HASH_TABLE_T * 待遍历的Hash表 
    HASH_IT_T    * Hash表迭代器

  输出参数：
    无

  返回值：
    Hash表的迭代器
 *****************************************************************************/
HASH_IT_T *iterateHash(HASH_TABLE_T *pstHash, HASH_IT_T *pstHashIt)
{
    HASH_IT_T *pstIter;

    if (pstHashIt == NULL)
    {
        pstIter = (HASH_IT_T *)malloc(sizeof(HASH_IT_T));
        pstIter->iIndex = -1;
        pstIter->pstBucket = NULL;
        pstIter->pstPrevBucket = NULL;
    }
    else
    {
        pstIter = pstHashIt;
    }

    /* 内存可用性检查，避免在最后一次迭代时删除了迭代器中的pstBucket */
    if (pstIter->pstBucket != NULL)
    {
        if (pstIter->pstFirstBucket != NULL)
        {
            /* 我们位于链表的头节点上，在最后一次迭代时将删除头节点 */
            if ((*pstIter->pstFirstBucket) != pstIter->pstBucket)
            {
                /* 当前链表上仍有其他节点 */
                if ((*pstIter->pstFirstBucket) != NULL)
                {
                    pstIter->pstPrevBucket = NULL;
                    pstIter->pstBucket = (*pstIter->pstFirstBucket);
                    pstIter->pstFirstBucket = &pstHash->pstTable[pstIter->iIndex];
                    return pstIter;
                }
                else
                {
                    pstIter->pstBucket = NULL;
                }
            }
        }
        else if (pstIter->pstPrevBucket != NULL)
        {
            /* 我们不位于链表的头节点上 */
            if (pstIter->pstPrevBucket->pstNext != pstIter->pstBucket)
            {
                pstIter->pstPrevBucket = pstIter->pstPrevBucket;
            }
        }
    }

    /* 跳到下一个节点 */
    if (pstIter->pstBucket != NULL)
    {
        if (pstIter->pstBucket->pstNext != NULL)
        {
            pstIter->pstPrevBucket = pstIter->pstBucket;
            pstIter->pstBucket = pstIter->pstBucket->pstNext;
            pstIter->pstFirstBucket = NULL;
            return pstIter;
        }

    }

    pstIter->iIndex ++;

    while ( pstIter->iIndex < pstHash->iSize) /* 遍历Hash表中的所有Key,找到第一个有存储数据的hash节点 */
    {
        if ((pstHash->pstTable[pstIter->iIndex]) != NULL)
        {
            pstIter->pstPrevBucket = NULL;
            pstIter->pstBucket = pstHash->pstTable[pstIter->iIndex];
            pstIter->pstFirstBucket = &pstHash->pstTable[pstIter->iIndex];
            return pstIter;
        }
        else
        {
            pstIter->iIndex++;
        }
    }

    free(pstIter);

    return NULL;

}

/******************************************************************************
  函数名：newHashTable
  功能描述：
    创建一个Hash表  

  输入参数：
    int            Hash表的容量大小
    HASH_COMP_CB   Hash比较回调函数 
    HASH_CHOOSE_CB 在Hash链表中查找可用存储节点
    HASH_FREE_CB   Hash节点数据内存释放回调函数指针

  输出参数：
    无

  返回值：
    成功时返回容量大小为iSize的Hash表结构体指针HASH_TABLE_T *
    失败时返回NULL
 *****************************************************************************/
HASH_TABLE_T *newHashTable(int iSize, HASH_COMP_CB pfnHashCmpCb, HASH_CHOOSE_CB pfnHashChooseCb, HASH_FREE_CB pfnHashFreeCb)
{
    HASH_TABLE_T *pstHash;

    pstHash = (HASH_TABLE_T *)malloc(sizeof(HASH_TABLE_T));
    if(pstHash == NULL)
    {
        return NULL;
    }

    pstHash->iSize = iSize;
    pstHash->pstTable = (HASH_NODE_T **)malloc(sizeof(HASH_NODE_T *) * iSize);
    if(pstHash->pstTable == NULL)/* Hash表节点内存分配失败 */
    {
        free(pstHash); /* 释放Hash链表的内存，避免mem leak */
        return NULL;
    }

    initHash(pstHash);

    pstHash->pifnCompare = pfnHashCmpCb;
    pstHash->pifnChoose  = pfnHashChooseCb;
    pstHash->pfnFree     = pfnHashFreeCb;
    pstHash->iElements   = 0;

    return pstHash;

}



/******************************************************************************
  函数名：addToHash
  功能描述：
    将数据散列到Hash表内 

  输入参数：
    HASH_TABLE_T * Hash表指针
    void *       待加入数据

  输出参数：
    无

  返回值：
    成功加入时返回                     ADD_HASH_OK     0
    由于键值冲突而导致加入失败返回     COLLISION_FOUND -1
    由于内存分配失败而导致加入失败返回 MALLOC_FAILED   -2
 *****************************************************************************/
int addToHash(HASH_TABLE_T *pstHash, void *pData)
{
    int iIndex;
    HASH_NODE_T *pstBucket = NULL;
    HASH_NODE_T *pstPrevBucket = NULL;
    
    int iRehash = 0;
    iIndex = pstHash->pifnChoose( pData, pstHash->iSize);
    pstBucket = pstHash->pstTable[iIndex];

    while (pstBucket != NULL)
    {
        while(HASH_KEY_MATCH != pstHash->pifnCompare( pstBucket->pData, pData)) 
        {
            if (iRehash < pstHash->iSize)
            {

                iIndex = (++iRehash + iIndex) % pstHash->iSize; /* 线性步进探测空slot */
                pstBucket = pstHash->pstTable[iIndex];
                if (pstBucket == NULL) /* found a slot! */
                {
                    break;
                }
                /* 不同的Key键值却映射到了同一个index，说明Hash算法产生了碰撞 */
                log_r(LOG_DEBUG, "hash collision occured and try rehash again with %d attempts!\n", iRehash);
            }
            else
            {
                log_r(LOG_DEBUG, "hash collision can not be resolved!\n");
                return COLLISION_FOUND;
            }

        }
        if (pstBucket != NULL)
        {
            pstPrevBucket = pstBucket;
            pstBucket = pstBucket->pstNext;
        }
    }

    /* 查找到了链表的结尾，加入新节点 */
    if (NULL == (pstBucket = (HASH_NODE_T *)malloc(sizeof(HASH_NODE_T))))
    {
        return MALLOC_FAILED;
    }

    pstBucket->pData = pData;
    pstBucket->pstNext = NULL;

    if( pstPrevBucket == NULL)
    {
        pstHash->pstTable[iIndex] = pstBucket;
    }
    else
    {
        pstPrevBucket->pstNext = pstBucket;
    }

    pstHash->iElements ++;

    return ADD_HASH_OK;

}

/******************************************************************************
  函数名：findInHash
  功能描述：
    在Hash表中按照数据内容进行查找

  输入参数：
    HASH_TABLE_T * Hash表指针
    void *         Hash节点数据结构

  输出参数：
    无

  返回值：
    成功时返回和待查找数据的KEY相同KEY对应的Hash表节点内容
    失败时返回NULL
 *****************************************************************************/
HASH_NODE_T *findInHash(HASH_TABLE_T *pstHash, void *pData)
{
    int iIndex;
    int iRehash = 0;
    HASH_NODE_T *pstBucket;

    iIndex = pstHash->pifnChoose(pData, pstHash->iSize);

    while (iRehash < pstHash->iSize)
    {
        iIndex = (iRehash++ + iIndex) % pstHash->iSize;
        pstBucket = pstHash->pstTable[iIndex];

        if (pstBucket != NULL)
        {
            if (HASH_KEY_MATCH == pstHash->pifnCompare(pstBucket->pData, pData))
            {
                return pstBucket;
            }
        }
    }

    return NULL;
}

/******************************************************************************
  函数名：removeBucketInHash
  功能描述：
    通过Hash迭代器，释放Hash表中指定节点的内存 

  输入参数：
    HASH_TABLE_T * Hash表结构体指针
    HASH_IT_T *    Hash迭代器结构体指针
  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
void removeBucketInHash(HASH_TABLE_T *pstHash, HASH_IT_T *pstHashIt)
{
    if (pstHashIt->pstBucket == NULL)
    {
        return ; 
    }

    void *pDataSave;

    pDataSave = pstHashIt->pstBucket->pData;

    if (pstHashIt->pstPrevBucket != NULL)
    {
        pstHashIt->pstPrevBucket->pstNext = pstHashIt->pstBucket->pstNext;
    }
    else if (pstHashIt->pstFirstBucket != NULL)
    {
        (*pstHashIt->pstFirstBucket) = pstHashIt->pstBucket->pstNext;
    }

    if (pstHash->pfnFree != NULL) /* 如果Hash节点数据有内存释放函数，则先调用之 */
    {
        dbgprint("call pstHash->pfnFree in removeBucketInHash!\n");
        pstHash->pfnFree(pDataSave);
    } 

    free(pstHashIt->pstBucket);
    
    dbgprint("removeBucketInHash ok!\n");

    pstHash->iElements--;

    return;
}

/******************************************************************************
  函数名：removeHash
  功能描述：
    在Hash表中删除指定的数据 

  输入参数：
    HASH_TABLE_T * Hash表结构体指针
    void *         待删除的数据
  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
void removeHash(HASH_TABLE_T *pstHash, void *pData)
{
    HASH_IT_T pstHashIt;

    int iRehash = 0;
    pstHashIt.iIndex = pstHash->pifnChoose(pData, pstHash->iSize);
    while (iRehash < pstHash->iSize)
    {
        pstHashIt.iIndex = (pstHashIt.iIndex + iRehash++) % pstHash->iSize;
        pstHashIt.pstBucket = pstHash->pstTable[pstHashIt.iIndex];
        pstHashIt.pstPrevBucket = NULL;

        while (pstHashIt.pstBucket != NULL)
        {
            if (HASH_KEY_MATCH == pstHash->pifnCompare(pstHashIt.pstBucket->pData, pData)) /* 找到*/
            {
                pstHashIt.pstFirstBucket = (pstHashIt.pstBucket == pstHash->pstTable[pstHashIt.iIndex] ? 
                        &pstHash->pstTable[pstHashIt.iIndex] : NULL);
                dbgprint("removeHash ok!\n");

                return removeBucketInHash(pstHash, &pstHashIt);
            }
            pstHashIt.pstPrevBucket = pstHashIt.pstBucket;
            pstHashIt.pstBucket = pstHashIt.pstBucket->pstNext;
        }
    }

    return ;
}

/******************************************************************************
  函数名：resizeHash
  功能描述：
    重新调整Hash表的容量 

  输入参数：
    HASH_TABLE_T * 待调整的Hash表结构体指针  
    int            Hash表容量增量

  输出参数：
    无

  返回值：
    成功时返回调整后的Hash表结构体指针
    失败时返回NULL
 *****************************************************************************/
HASH_TABLE_T *resizeHash(HASH_TABLE_T *pstHash, int iSize)
{
    HASH_TABLE_T *pstNewHash;
    HASH_NODE_T  *pstBucket;
    int i;
    int iOldSize;

    iOldSize = pstHash->iSize;

    if ( NULL == (pstNewHash = newHashTable(iSize + iOldSize, pstHash->pifnCompare, pstHash->pifnChoose, pstHash->pfnFree)))
    {
        return NULL;
    }

    for (i = 0; i < pstHash->iSize; i++)
    {
        pstBucket = pstHash->pstTable[i];
        while (pstBucket != NULL)
        {
            switch(addToHash(pstNewHash, pstBucket->pData))
            {
                case ADD_HASH_OK:

                    break;
                case COLLISION_FOUND: /*TOFIX 异常处理 */
                    log_r(LOG_DEBUG," collison found in %s:%s %d", __FILE__, __FUNCTION__, __LINE__);
                    break;
                case MALLOC_FAILED:   /*TOFIX 异常处理 */
                    log_r(LOG_DEBUG," malloc failed in %s:%s %d", __FILE__, __FUNCTION__, __LINE__);
                    break;
                default:

                    break;
            }
            pstBucket = pstBucket->pstNext;
        }
    }
    deleteHash(pstHash, DISABLE_FREE_DATA_CB); 

    return pstNewHash;

}


/******************************************************************************
  函数名：debugHash
  功能描述：
    Hash表结构体指针打印函数，仅供调试用

  输入参数：
    HASH_TABLE_T * Hash表结构体指针

  输出参数：
    无

  返回值：
    无
 *****************************************************************************/
void debugHash(HASH_TABLE_T *pstHash)
{
    int i;
    HASH_NODE_T *pstBucket;

    for(i = 0; i < pstHash->iSize; i++)
    {
        log_r(LOG_DEBUG, "[%d] ", i);
        pstBucket = pstHash->pstTable[i];

        while (pstBucket != NULL)
        {
            log_r(LOG_DEBUG, "-> [%10p] ", pstBucket);
            log_r(LOG_DEBUG, "-> %s ", (char *)pstBucket->pData); /* 仅支持字符串的打印 */
            pstBucket = pstBucket->pstNext;
        }

        log_r(LOG_DEBUG, "\n");
    }

    log_r(LOG_DEBUG, "\n");
}

